#include<iostream>
#include<string>
#include<vector>


int KMP(std::string a, std::string b) {
	int n = a.size();
	int m = b.size();
	std::vector<int> next(m);
	next[0] = -1;
	int i = 0, j = -1;
	while (i < m - 1) {
		if (j == -1 || b[i] == b[j]) next[++i] = ++j;
		else j = next[j];
	}

	i = 0;
	j = 0;
	while (i < n && j < m) {
		if (j == -1 || a[i] == b[j]) {
			++i;
			++j;
		}
		else {
			j = next[j];
		}
	}
	
	return j == m ? i - j : -1;
}

int main() {
	std::string a = "leetcode";
	std::string b = "leeto";
	std::cout << KMP(a, b) << std::endl;
	return 0;
}